package leetcode_cn;

import java.util.Arrays;

/**
 * 两个排序数组的中位数
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-09-04 16:44
 */
public class FindMedianSortedArrays {

    public double solution(int[] nums1,int[] nums2){
        int len1 = nums1==null?0:nums1.length;
        int len2 = nums2==null?0:nums2.length;
        int[] array = new int[len1 + len2];
        int l1 = 0,l2 = 0;
        for (int i = 0; i < len1+len2; i++) {
            if (l1 == len1){
                array[i] = nums2[l2++];
                continue;
            }
            if (l2 == len2){
                array[i] = nums1[l1++];
                continue;
            }

            array[i] = nums1[l1] <= nums2[l2] ? nums1[l1++]:nums2[l2++];
        }
        int mid = array.length / 2;
        if (array.length % 2 != 0)
            return array[mid];
        else return (array[mid] + array[mid-1]) / 2.0;
    }

    public static void main(String[] args) {
        FindMedianSortedArrays f = new FindMedianSortedArrays();
//        int[] array = new int[]{15, 0, 6, 9, 3};
        Comparable[] array = new Comparable[]{15, 0, 6, 9, 3};
        f.sort(array);
        System.out.println("");
    }

    public void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while (h < N / 3){
            h = h*3 + 1;
        }

        while (h >=1){
            for (int i = h; i < N; i++) {
                for (int j = i; j >=h && compareElement(a[j],a[j-h]); j -= h) {
                    exch(a,j,j-h);
                }
            }
            h = h / 3;
        }
    }

    public boolean compareElement(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }

    public void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];a[i] = a[j];a[j] = t;
    }
}
